\begin{problem}{Molecule. Химия!!!}{molecule.in}{molecule.out}{1 секунда}{64 мегабайта}

Вася и Сережа играют в следующую игру. В некоторых клетках клетчатого листка Сережа рисует один из 
символов `\texttt{H}', `\texttt{O}', `\texttt{N}' или `\texttt{C}', после чего Вася должен провести между некоторыми
находящимися в соседних клетках символами линии так, чтобы получилось корректное изображение
химической молекулы. К сожалению, Сережа любит рисовать много символов, и Вася не может сразу
определить, возможно ли вообще нарисовать линии нужным способом. Помогите ему написать программу,
которая даст ответ на этот вопрос.

В этой задаче проведенные между символами химических элементов линии будем считать корректным изображением молекулы,
если они удовлетворяют следующим условиям:
\begin{itemize}
\item каждая линия соединяет символы, нарисованные в соседних (по стороне) клетках, 
\item между каждой парой символов проведено не более одной линии,
\item от каждого элемента отходит ровно столько линий, какова валентность этого элемента (1 для H, 2 для O, 3 для N, 4 для C), 
\item пустые клетки ни с чем не соединены, и
\item хотя бы в одной клетке нарисован какой-то символ.
\end{itemize}


\InputFile

Первая строка входного файла содержит два натуральных числа $n$ и $m$ ($1\leq n,m\leq 50$) "--- размеры листочка, на котором рисует Сережа.
Далее следуют $n$ строк по $m$ символов в каждой, задающих конфигурацию химических элементов, которую нарисовал Сережа;
пустые клетки задаются символом `\texttt{.}'.

\OutputFile

В выходной файл выведите одно слово: `\texttt{Valid}', если линии провести требуемым образом можно, и `\texttt{Invalid}',
если нельзя.

\Example

 \begin{example}
\exmp{
3 4
HOH.
NCOH
OO..
}{
Valid
}%
\exmp{
3 4
HOH.
NCOH
OONH
}{
Invalid
}%
\end{example}

\end{problem}